package pyip.lib.javalearn.algorithm.sort;

/**
 * 快速排序<br>
 * 基本思想：选择一个基准元素, 通常选择第一个元素或者最后一个元素, 通过一趟扫描，将待排序列分成两部分, 一部分比基准元素小, 一部分大于等于基准元素, <br>
 * 此时基准元素在其排好序后的正确位置, 然后再用同样的方法递归地排序划分的两部分。
 * @author yepeng
 * @date 2015年9月2日
 */
public class QuickSort implements Sort {

    @Override
    public void sort(int[] arr, boolean asc) {
        if (arr != null && arr.length > 1) {
            quickSort(arr, 0, arr.length - 1);
        }
    }

    private static void quickSort(int[] list, int low, int high) {
        if (low < high) {
            int middle = getMiddle(list, low, high); // 将list数组进行一分为二
            quickSort(list, low, middle - 1); // 对低字表进行递归排序
            quickSort(list, middle + 1, high); // 对高字表进行递归排序
        }
    }

    private static int getMiddle(int[] list, int low, int high) {
        int temp = list[low]; // 数组的第一个作为中轴
        while (low < high) {
            while (low < high && list[high] >= temp) {
                high--;
            }
            list[low] = list[high]; // 比中轴小的记录移到低端
            while (low < high && list[low] <= temp) {
                low++;
            }
            list[high] = list[low]; // 比中轴大的记录移到高端
        }
        list[low] = temp; // 中轴记录到尾
        return low; // 返回中轴的位置
    }

}
